package com.fun.arithmetic;

/**
 * 反转链表
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = solution.getInitListNode();
        //ListNode reverseList = solution.reverseList(head);
        ListNode reverseList = solution.reverseList2(head);
        reverseList.print();
    }

    /**
     * 非递归方法
     * 1->2->3->null
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        //指向前的节点，类似于一个指针
        ListNode pre = null;
        //当前节点
        ListNode cur = head;

        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    public ListNode reverseList2(ListNode head){
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public ListNode getInitListNode() {
        ListNode listNode = new ListNode(1);
        listNode.next = new ListNode(2);
        listNode.next.next = new ListNode(3);
        return listNode;
    }

    static class ListNode {
        private int val;
        private ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        public void print(){
            ListNode innerNext = this;
            while (innerNext!=null){
                System.out.println(innerNext.val);
                innerNext = innerNext.next;
            }
        }
    }
}
